package arbre.utils;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
//import com.sun.corba.se.impl.orbutil.graph.Node;

public class ArbreBinaire implements Serializable{
	public static int SENS_GAUCHE=-1;
	public static int SENS_DROITE=1;
	public static int SENS_HAUT=100;
	public static int SENS_BAS=-100;
	private Noeud r;
	
	private float epsilon;


	public ArbreBinaire(){
		//dio nothing
	}
	/**
	 * Contructeur de l'arbre de d��cision, �� partir d'une liste de segments.
	 * 
	 * @param segments 	: la liste des segments 
	 */
	public ArbreBinaire(List<Segment> segments){
		

		List<Point> points = toPointsTries(segments);
		List<Verticale> verticales = new ArrayList<Verticale>();

		// On trace les perpendiculaire
		int id = 0;
		for(Point p : points){
			Verticale v = new Verticale(p);
			v.setId(id);
			id++;
			verticales.add(v);
		}



		//On ajoute les segments qui sont entre les perpendiculaire
		for(int i =0; i< verticales.size();i++){
			//verticales.get(i).trouverintersection(segments, verticales.get(i+1));
			//verticales.get(i).showIntersection();
			if(i==0){
				//pas de gauche
				verticales.get(i).setPrecedente(null);
				verticales.get(i).setSuivante(verticales.get(i+1));
			}
			else if(i==verticales.size()-1){
				//pas de droite
				verticales.get(i).setPrecedente(verticales.get(i-1));
				verticales.get(i).setSuivante(null);
			}
			else{
				verticales.get(i).setPrecedente(verticales.get(i-1));
				verticales.get(i).setSuivante(verticales.get(i+1));
			}
		}

		r =  construireArbre(segments,verticales,null, 0,verticales.size()-1, 0);
		System.out.println("----------");
		//System.out.println(racine/*.toDot()*/);

		//		save();

	}

	

	/**
	 * 
	 * @param segments 
	 * @param verticales 	: Liste des verticales
	 * @param pred 			: Noeud pr��d��cesseur du node courant 
	 * @param debut			: d��but du tableau consid��r��
	 * @param fin			: fin du tableau consid��r��
	 * @return 				: Noeud racine du sous arbre courant
	 */
	private Noeud construireArbre(List<Segment> segments, List<Verticale> verticales, Noeud pred,
			int debut, int fin, int dir) {

		int taille = mysize(debut,fin);
		if(taille <0){
			Noeud  res;
			//System.out.println("appel feuille (fin < debut) au niveau de  : " + pred.toString()+", deb: "+debut +", fin: "+fin +", dir =" + dir);
			//trouver intersections 
			try{
				if(dir == SENS_GAUCHE){
					if(fin >0){
						List<Segment> interGauche = verticales.get(fin).trouverintersection(segments, verticales.get(fin-1));
						Collections.sort(interGauche);
						res = construireP2arbre(interGauche, pred, 0, interGauche.size()-1, SENS_GAUCHE);
						return res;
					}
					else{
						//TODO
						//ici , on a depass��, et la fin ==0, donc pas de verticale a gauche, 
						//trouver la zone (souvent zone ext��rieure)
					}
				}
				else if(dir == SENS_DROITE){

					if(fin < verticales.size()-1){
						//System.out.println("cas bizarre I sens droit");
						List<Segment> interDroite = verticales.get(fin).trouverintersection(segments, verticales.get(debut));
						Collections.sort(interDroite);
						//System.out.println("cas bizarre droit :"+interDroite.size());
						res = construireP2arbre(interDroite, pred, 0, interDroite.size()-1, SENS_DROITE);
						return res;
					}
					else{
						/*
						 * TODO
						 * ici , on a d��pass�� a droite, trouver la zone correspondante
						 */

					}
				}

			}catch (Exception e){
				e.printStackTrace();
			}
			return null;
		}
		else if(taille == 0){

			//feuille arbre I , car je ne me regarde que moi, 
			//trouver les intersections DONE
			//construire les sous-arbres de type II --done

			Noeud res= new Noeud(null, null, pred, new ContentNode("v",""+debut,verticales.get(debut).getAbs(),null,null),dir);

			if(debut < verticales.size()-1){
				List<Segment> interDroite = verticales.get(debut).trouverintersection(segments, verticales.get(debut+1));
				Collections.sort(interDroite);
				res.setR(construireP2arbre(interDroite, res, 0, interDroite.size()-1, SENS_DROITE));
			}
			if(debut >0){
				List<Segment> interGauche = verticales.get(debut).trouverintersection(segments, verticales.get(debut-1));
				Collections.sort(interGauche);
				res.setL(construireP2arbre(interGauche, res, 0, interGauche.size()-1, SENS_GAUCHE));
			}
			//System.out.println(res.getContent().toString() + "pred: "+ pred.getContent().toString());
			return res;

		}
		else{
			int med = mediane(debut,taille);

			Noeud me = new Noeud(null, null, pred, new ContentNode("v", ""+med,verticales.get(med).getAbs(),null,null),dir);
			Noeud nLeft = construireArbre(segments, verticales, me, debut, med-1, SENS_GAUCHE);
			Noeud nRight = construireArbre(segments, verticales, me, med+1, fin, SENS_DROITE);
			me.setL(nLeft);
			me.setR(nRight);
			return me;
		}
	}

	/**
	 * m��thode qui retourne les secondes parties de l'arbre, a savoir les noeuds qui corespondent
	 * aux segments qui intersectent les verticales.
	 *  
	 * @param intersections :  liste des segments traversant les verticales
	 * @param pred 			: noeud pr��d��cesseurs, celui qui fait l'appel r��cursif
	 * @param debut 		: premier index 
	 * @param fin 			: dernier index
	 * @return un sous arbre qui contient les horizontales comme noeud, et en feuilles les zones
	 */
	private Noeud construireP2arbre(List<Segment> intersections, Noeud pred,
			int debut, int fin, int dir) {

		int taille = mysize(debut, fin);
		if(taille < 0){
			// TODO g��rer cas ��trange
			//System.out.println("appel cas bizarre pII (fin < debut) au niveau de  : " + pred.toString()+", deb: "+debut +", fin: "+fin +", dir =" + dir);
			try {
				/*
				 * 
				 * on arrive sur un segment qui n'as plus de fils
				 * il faut donc trouver sa zone fille, et cela depend de la direction d'appel
				 * le segment de r��f��rence est celui qui envoie dnas cette boucle, ici fin
				 * 
				 */
				if(dir == SENS_HAUT){
					return new Noeud(null, null, pred,new ContentNode("z", intersections.get(fin).getHaut().getNom(),-10000f,null,null) ,dir);
				}
				else if(dir == SENS_BAS){
					return new Noeud(null, null, pred,new ContentNode("z", intersections.get(fin).getBas().getNom(),-10000f,null,null),dir);
				}

			} catch (Exception e) {
				e.printStackTrace();
			}
			return null;
		}
		else if(taille == 0){


			Noeud res = new Noeud(null, null, pred,new ContentNode("s", intersections.get(debut).getId(),-10000f,intersections.get(debut).getDebut(),intersections.get(debut).getFin()),dir);
			Noeud left = new Noeud(null, null, res,new ContentNode("z", intersections.get(debut).getBas().getNom(),-10000f,null,null),SENS_BAS);
			Noeud right = new Noeud(null, null, res,new ContentNode("z", intersections.get(debut).getHaut().getNom(),-10000f,null,null),SENS_HAUT);
			res.setL(left);
			res.setR(right);
			//System.out.println("fils PII : "+ ((Segment)res.getContent()).toString()+", left : "+left.getContent()+", rigth : "+ right.getContent());
			return res;
		}
		else{
			int med = mediane(debut,taille);
			Noeud me = new Noeud(null, null, pred,new ContentNode("s", intersections.get(med).getId(),-10000f,intersections.get(med).getDebut(),intersections.get(med).getFin()),dir);
			Noeud left = construireP2arbre(intersections, me, debut, med-1, SENS_BAS);
			Noeud right = construireP2arbre(intersections, me, med+1, fin, SENS_HAUT);
			me.setL(left);
			me.setR(right);
			return me;
		}
	}

	/**
	 * m��thode qui renvoie la taille entre deux index deux tableaux
	 * @param debut
	 * @param fin
	 * @return la taille
	 */
	private int mysize(int debut, int fin) {
		if(debut <= fin){
			return fin-debut;
		}
		//System.err.println("gaffe");
		return -1;
	}

	/**
	 * la m��diane d'un tableau avec l'index du debut et la taille du tableau
	 * @param debut
	 * @param size
	 * @return
	 */
	private int mediane(int debut,int size) {
		if(size % 2 == 0){
			//size paire
			return debut+size/2;
		}
		else{
			return debut+(size/2)+1;
		}
	}


	/**
	 * @param segments
	 * @return la liste des points triees 
	 * cree un set de point triee, a partir d'un ensemble de segment  
	 */
	private static ArrayList<Point> toPointsTries(List<Segment> segments) {
		ArrayList<Point> points = new ArrayList<Point>();

		for(Segment s : segments){
			points.add(s.getDebut());
		}
		//l�� on a ajout�� tous les points
		Collections.sort(points);
		//System.out.println(points);
		return points;
	}

	

	public static void main(String[] arg) {

		ArrayList<Segment> segments = new ArrayList<Segment>();
		//		//ab
		//		segments.add(new Segment(new Point(0.0f, 0.0f)/*A*/, new Point(2.0f, 1.0f)/*B*/));
		//		//bc
		//		segments.add(new Segment(new Point(2.0f, 1.0f)/*B*/, new Point(-1.5f, 1.0f)/*C*/));
		//		//cd
		//		segments.add(new Segment(new Point(-1.5f, 1.0f)/*C*/, new Point(-2.0f, -2.0f)/*D*/));
		//		//de
		//		segments.add(new Segment(new Point(-2.0f, -2.0f)/*D*/, new Point(2.5f, -2.0f)/*E*/));
		//		//ef
		//		segments.add(new Segment(new Point(2.5f, -2.0f)/*E*/, new Point(-1.0f, -1.0f)/*F*/));
		//		//fg
		//		//segments.add(new Segment(new Point(-1.0f, -1.0f)/*F*/, new Point(1.0f, -1.0f)/*G*/));
		//		//ga
		//		//segments.add(new Segment(new Point(1.0f, -1.0f)/*G*/, new Point(0.0f, 0.0f)/*A*/));
		//		//test localizer
		//		segments.add(new Segment(new Point(-1.0f, -1.0f)/*F*/, new Point(0.0f, 0.0f)/*A*/));

		Zone polyTest = new Zone("Poly");
		Zone dehors = new Zone("Dehors");
		//12
		segments.add(new Segment(new Point(0.0f, 0.0f)/*1*/, new Point(2.0f, 1.0f)/*2*/));
		//15
		segments.get(segments.size()-1).setId("1");
		segments.get(segments.size()-1).setBas(polyTest);
		segments.get(segments.size()-1).setHaut(dehors);
		segments.add(new Segment(new Point(2.0f, 1.0f)/*2*/, new Point(4.0f, 0.5f)/*5*/));
		//54
		segments.get(segments.size()-1).setId("2");
		segments.get(segments.size()-1).setBas(polyTest);
		segments.get(segments.size()-1).setHaut(dehors);
		segments.add(new Segment(new Point(4.0f, 0.5f)/*5*/, new Point(3.0f, -0.5f)/*4*/));
		//43
		segments.get(segments.size()-1).setId("3");
		segments.get(segments.size()-1).setBas(dehors);
		segments.get(segments.size()-1).setHaut(polyTest);
		segments.add(new Segment(new Point(3.0f, -0.5f)/*4*/, new Point(2.5f,-2.0f)/*3*/));
		//31
		segments.get(segments.size()-1).setId("4");
		segments.get(segments.size()-1).setBas(dehors);
		segments.get(segments.size()-1).setHaut(polyTest);
		segments.add(new Segment(new Point(2.5f, -2.0f)/*3*/, new Point(0.0f, 0.0f)/*1*/));
		segments.get(segments.size()-1).setId("5");
		segments.get(segments.size()-1).setBas(dehors);
		segments.get(segments.size()-1).setHaut(polyTest);
		ArbreBinaire ar = new ArbreBinaire(segments);

		Point test = new Point(1.5f, -1.0f);
		System.out.println(ar.localiser(test).getC());

	}

	public Noeud getRacine() {
		return r;
	}

	public void setRacine(Noeud racine) {
		this.r = (Noeud)racine;
	}

	@Override
	public String toString() {
		return "<arbre>\n"
				+ r.toString()
				+ "</arbre>";
	}

	public float getEpsilon() {
		return epsilon;
	}
	public void setEpsilon(float epsilon) {
		this.epsilon = epsilon;
	}

	public Noeud localiser(Point p){
		Noeud res = find(r, p);
		return res;

	}
	private Noeud find(Noeud n, Point p) {

		Object r= n.getC();
		System.out.println(r.getClass().getName());
		//si pas de fils, alors feuille on return 
		if(n.getL()==null && n.getR()==null){
			return n;
		}
		else{

			/*
			 * trois cas,
			 * soit verticale,
			 * soit segment,
			 * soit zone
			 */

			if(r instanceof Verticale){
//				if(p.getX() <= ((Verticale)n.getContent()).getAbs()){
//					if(n.getLeft()!=null){
//						System.out.println("left de "+n.getContent()+", " + p);
//						return find(n.getLeft(),p);
//					}
//				}
//				else if(p.getX() > ((Verticale)n.getContent()).getAbs()){
//					if(n.getRight()!=null){
//						System.out.println("right" +n.getContent()+", "+ p);
//						return find(n.getRight(),p);
//					}
//				}

			}
			else if (r instanceof Segment){
				System.out.println(r);
				//				if(((Segment)n.getContent()).sur(p)){
				//					return n;
				//				}
				//				else
//				if(((Segment)n.getContent()).dessous(p)){
//					if(n.getLeft()!=null){
//						System.out.println("segleft" + p);
//						return find(n.getLeft(),p);
//					}
//					else{
//						System.out.println("segleft = null");
//					}
//				}
//				else if(((Segment)n.getContent()).dessus(p)){
//					if(n.getRight()!= null){
//						System.out.println("segRight" + p);
//						return find(n.getRight(),p);
//					}
//					else{
//						System.out.println("segRigth = null");
//					}
//				}

			}
			else if (r instanceof Zone){
				return n;
			}
			else{
				return null;
			}

		}
		return null;
	}

	public static int getSensGauche() {
		return SENS_GAUCHE;
	}
	public static int getSensDroite() {
		return SENS_DROITE;
	}
	public static int getSensHaut() {
		return SENS_HAUT;
	}
	public static int getSensBas() {
		return SENS_BAS;
	}
	public static void setSensGauche(int sensGauche) {
		SENS_GAUCHE = sensGauche;
	}
	public static void setSensDroite(int sensDroite) {
		SENS_DROITE = sensDroite;
	}
	public static void setSensHaut(int sensHaut) {
		SENS_HAUT = sensHaut;
	}
	public static void setSensBas(int sensBas) {
		SENS_BAS = sensBas;
	}
	public int taille() {
		if (r != null){
			return r.taille();
		}
		else return -1;
	}


}
